#ifndef __DOUBLELINKLIST_HPP_
#define __DOUBLELINKLIST_HPP_

#include <iostream>
template<typename T>
class DoubleLinkList
{
public:
/* 构造 */
    DoubleLinkList();
    ~DoubleLinkList();
/* 尾插 */
    void InsertTail(const T & value);
/* 头插 */
    void InsertHead(const T & value);
    void RemoveHead();
    T & GetHead();
    int Size();

/* 重载<< 声明 */
    template<typename U>
    friend std::ostream & operator<<(std::ostream& os, const DoubleLinkList<U>& list);

private:
    struct Node
    {
        /* Node构造函数 */
        Node(const T & data)
        {
            this->data = data;
            next = prev = nullptr;
        }
        /* 变量 */
        T data;
        Node * next;
        Node * prev;
    };
    /* 获取根节点 */
    Node * GetEnd()
    {
        Node * travelPoint = head;
        while(travelPoint->next != nullptr)
        {
            travelPoint = travelPoint->next;
        }
        return travelPoint;
    }

    Node * head;
    int size;
};


template<typename T>
DoubleLinkList<T>::DoubleLinkList():size(0)
{
    head = new Node(T());    //匿名对象 int() = 0;std::string() = nullptr
    head->next = head->prev  = nullptr;
}

template<typename T>
DoubleLinkList<T>::~DoubleLinkList()
{
    while(head != nullptr)
    {
        Node * temp = head->next;
        delete head;
        head = temp;
    }
}

template <typename T>
inline void DoubleLinkList<T>::InsertTail(const T &value)
{
    Node * newNode = new Node(value);
    Node * end = GetEnd();
    end->next = newNode;
    newNode->prev = end;
    size++;
}

template <typename T>
inline void DoubleLinkList<T>::InsertHead(const T &value)
{
    Node * newNode = new Node(value);
    newNode->next = head->next;
    newNode->prev = head;
    if(head->next)
        head->next->prev = newNode;
    head->next = newNode;
    size++;
}

template <typename T>
inline void DoubleLinkList<T>::RemoveHead()
{
    if(head->next == nullptr)
        return;
    Node * freeNode = head->next;
    head->next = freeNode->next;
    if(freeNode->next)
        freeNode->next->prev = head;
    delete freeNode;
    size--;
}

template <typename T>
inline T &DoubleLinkList<T>::GetHead()
{
    return head->next->data;
}

template <typename T>
inline int DoubleLinkList<T>::Size()
{
    return size;
}

template <typename U>
inline std::ostream &operator<<(std::ostream &os, const DoubleLinkList<U> &list)
{
    //typename 声明后面所跟的参数是一个类型
    typename DoubleLinkList<U>::Node * travelPoint = list.head->next;
    while(travelPoint != nullptr)
    {
        os<<travelPoint->data<<" ";
        travelPoint = travelPoint->next;
    }
    os<<std::endl;
    return os;
}

#endif


